// 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

// 你应当 保留 两个分区中每个节点的初始相对位置。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
// 符合结果但没有保留相对位置
var partition = function(head, x) {
    let onehead = new ListNode(0);
    onehead.next = head;
    head = onehead;
    let res = head;
    let lastnode = new ListNode(0);
    let last = lastnode;
    let headnode = new ListNode(0);
    let bef = headnode;
    while (1) {
        if (res.val == x) {
            last.next = null;
            break;
        }
        if (res.next.val > x) {
            last.next = res.next;
            last = last.next;
            res.next = res.next.next;
        }
        res = res.next
    }
    while (1) {
        if (!res.next) { break; }
        if (res.next.val < x) {
            bef.next = res.next;
            bef = bef.next;
            res.next = res.next.next;
        } else {
            res = res.next
        }
    }
    head = head.next;
    lastnode = lastnode.next;
    bef.next = head;
    res.next = lastnode;
    return headnode.next
};

var partition = function(head, x) {
    let pA = a = new ListNode(0),
        pB = b = new ListNode(0)
    while (head) {
        head.val < x ? a = a.next = head : b = b.next = head
            //利用等号的处理顺序简化代码
        head = head.next
    }
    a.next = pB.next
    b.next = null //注意将后面链表的next置空
    return pA.next
};